/*
提交链接:https://leetcode.cn/problems/accounts-merge/description/
721. 账户合并
赖德檀 2024/10/8
*/

//先初始化每个账户为1个连通分量
// 遍历每个账户下的邮箱，判断该邮箱是否在其他账户下出现
// 如果未出现，继续
// 如果账户A、B下出现了相同的邮箱email,那么将账户A和账户B两个连通分量进行合并
// 最后遍历并查集中每个连通分量，将所有连通分量内部账户的邮箱全部合并(相同的去重，不同的合并)

class Solution {
public:
int* par;

void solu(int n)  //初始化
{
    par=new int[n];
    for(int i=0;i<n;i++)
    {
        par[i]=i;
    }
}

int find(int x)  //查
{
    if(par[x]!=x)
    {
        par[x]=find(par[x]);
    }
    return par[x];
}

void pair(int a,int b)  //并
{
    par[find(a)]=find(b);
} 

    vector<vector<string>> accountsMerge(vector<vector<string>>& accounts) {
        vector<vector<string>>s;
        unordered_map<string,int>mp;  //<邮箱,账户id>存储每个邮箱属于哪个账户,同时 在遍历邮箱时,判断邮箱是否出现过
        int n=accounts.size();
        solu(n);
        for(int i=0;i<n;i++)
        {
            int m=accounts[i].size();
            for(int j=1;j<m;j++)
            {
                string t=accounts[i][j];
                if(mp.find(t)==mp.end())
                mp[t]=i;
                else
                pair(i,mp[t]);  //一旦发现有邮箱重复的就合并id
            }
        }
        unordered_map<int, vector<string>>mp1; 
//<账户id, 邮箱列表> 存储每个账户下的邮箱  
//这里的key必须是账户id,不能是账户名称,名称可能相同,会造成覆盖
        for (auto& [a, b] : mp) 
        {
            mp1[find(b)].push_back(a); //同一个人邮箱合并到一个id中
        }
        for (auto& [a, b] : mp1){
            vector<string> kk(1, accounts[a][0]); //取名称
            sort(b.begin(), b.end());
            kk.insert(kk.end(), b.begin(), b.end());
            //在kk字符串数组的结尾插入b字符串数组
            s.push_back(kk);
        }
        return s;
    }
};